Việc Diffie, Hellman, Rivest, Shamir, và Adleman công bố công trình nghiên cứu về trao đổi khóa an toàn và thuật toán mật mã hóa khóa công khai vào năm 1976 đã làm thay đổi hoàn toàn cách thức trao đổi thông tin mật. Cùng với sự phát triển của các hệ thống truyền thông điện tử tốc độ cao (Internet và các hệ thống trước nó), nhu cầu về trao đổi thông tin bí mật trở nên cấp thiết. Thêm vào đó một yêu cầu nữa phát sinh là việc xác định định dạng của những người tham gia vào quá trình thông tin. Vì vậy ý tưởng về việc gắn định dạng người dùng với chứng thực được bảo vệ bằng các kỹ thuật mật mã đã được phát triển một cách mạnh mẽ.

Nhiều giao thức sử dụng các kỹ thuật mật mã mới đã được phát triển và phân tích. Cùng với sự ra đời và phổ biến của World Wide Web, những nhu cầu về thông tin an toàn và nhận thực người sử dụng càng trở nên cấp thiết. Chỉ tính riêng các nhu cầu ứng dụng cho thương mại (như giao dịch điện tử hay truy cập những cơ sở dữ liệu bằng trình duyệt web) cũng đã đủ hấp dẫn các nhà phát triển lĩnh vực này. Taher ElGamal và các cộng sự tại Netscape đã phát triển giao thức SSL (https trong địa chỉ web) trong đó bao gồm thiết lập khóa, nhận thực máy chủ... Sau đó, các thiết chế PKI được tạo ra để phục vụ nhu cầu truyền thông an toàn.

Các nhà doanh nghiệp kỳ vọng vào một thị trường hứa hẹn mới đã thành lập những công ty hoặc dự án mới về PKI và bắt đầu vận động các chính phủ để hình thành nên khung pháp lý về lĩnh vực này. Một dự án của American Bar Association đã xuất bản một nghiên cứu tổng quát về những vấn đề pháp lý có thể nảy sinh khi vận hành PKI (xem thêm: các hướng dẫn chữ ký số ABA). Không lâu sau đó, một vài tiểu bang của Hoa kỳ mà đi đầu là Utah (năm 1995) đã thông qua những dự luật và quy định đầu tiên. Các nhóm bảo vệ quyền lợi người tiêu dùng thì đặt ra các vấn đề về bảo vệ quyền riêng tư và các trách nhiệm pháp lý.

Tuy nhiên, các luật và quy định đã được thông qua lại không thống nhất trên thế giới. Thêm vào đó là những khó khăn về kỹ thuật và vận hành khiến cho việc thực hiện PKI khó khăn hơn rất nhiều so với kỳ vọng ban đầu.

Tại thời điểm đầu thế kỷ 21, người ta nhận ra rằng các kỹ thuật mật mã cũng như các quy trình/giao thức rất khó được thực hiện chính xác và các tiêu chuẩn hiện tại chưa đáp ứng được các yêu cầu đề ra.

Thị trường PKI thực sự đã tồn tại và phát triển nhưng không phải với quy mô đã được kỳ vọng từ những năm giữa của thập kỷ 1990. PKI chưa giải quyết được một số vấn đề mà nó được kỳ vọng. Những PKI thành công nhất tới nay là các phiên bản do các chính phủ thực hiện.